class Solution
{
public:
    // mul返回的是结果的逆序，便于相加
    string mul(const string &num, int x)
    {
        // 如果相乘的数是0，直接返回0即可
        if (!x)
            return "0";
        string tmp;
        int ed = num.size() - 1, top = 0;
        for (; ed >= 0; --ed)
        {
            int t = top;
            t += (num[ed] - '0') * x;
            top = t / 10;
            tmp += t % 10 + '0';
        }
        // cout << "mul\n";
        // cout << top << ' ' << tmp << endl;
        if (top)
            return tmp += char(top + '0');
        else
            return tmp;
    }
    void add(string &ans, const string &add, int k)
    {
        cout << add << endl;
        // 加上进位之后就是从第k位开始相加
        int ed1 = k, ed2 = 0, top = 0, now = k;
        size_t sz = ans.size();
        while (ed1 < sz || ed2 < add.size())
        {
            int t = top;
            if (ed1 < sz)
                t += ans[ed1] - '0', ed1++;
            if (ed2 < add.size())
                t += add[ed2] - '0', ed2++;
            top = t / 10;
            if (now < sz)
                ans[now++] = t % 10 + '0';
            else
                ans.push_back(t % 10 + '0');
        }
        // cout << ans << endl;
        // 最后也千万不能忘记进位
        if (top)
            ans += '1';
        // cout << "add\n";
    }
    string multiply(string num1, string num2)
    {
        // 记得加法需要进位
        string ans;
        int k = 0;
        if (num1.size() < num2.size())
            num1.swap(num2);
        if (num2 == "0" || num1 == "0")
            return "0";
        for (int i = num2.size() - 1; i >= 0; --i)
            add(ans, mul(num1, num2[i] - '0'), k++);
        // 删除前导0
        k = ans.size() - 1;
        while (ans[k] == '0')
            ans.pop_back(), --k;
        reverse(ans.begin(), ans.end());
        return ans;
    }
};